import java.util.*;

public class MyPriorityQueue<E extends Comparable<E>> {

    //成员变量的定义
    private Object[] arrays;
    private int size;
    private int DEFAULT_INITIALIZATION_CAPACITY = 8;//默认容量

    //构造函数
    public MyPriorityQueue(){
        arrays = new Object[DEFAULT_INITIALIZATION_CAPACITY];
    }
    public MyPriorityQueue(int capacity){
        if(capacity < 1) throw new IllegalArgumentException();
        arrays = new Object[capacity];
    }
    public MyPriorityQueue(Collection<? extends E> collection){
        int length = collection.size();
        arrays = new Object[length];

        Iterator<? extends E> iterable = collection.iterator();
//        for(E e : collection){
//            arrays[size++] = e;
//        }
        while(iterable.hasNext()){
            arrays[size++] = iterable.next();
        }
        for (int root = (size -2) / 2; root >= 0 ; root--) {
            siftDown(root);
        }
    }

    //向下调整
    public  void siftDown(int parent){

        int child = 2 * parent + 1;
        int size = this.size;

        while(child < size){
            //是否存在右孩子，存在找最小值
            E o = (E)arrays[child];
            if(child + 1 < size && o.compareTo((E)arrays[child + 1]) > 0){
                child = child + 1;//右孩子小
            }

            //交换
            E o1 = (E)arrays[parent];
            E o2 = (E)arrays[child];
            if(o1.compareTo(o2) > 0){
                Object t = arrays[parent];
                arrays[parent] = arrays[child];
                arrays[child] = t;
                //更新parent
                parent = child;
                child =  2 * parent + 1;
            }else break;

        }
    }

    public void siftUp(int child){
        int parent = (child - 1) / 2;
        //终止条件：parent >= 0 父节点下标不能越界 或者 child > 0 孩子节点为根节点，无需调整
        while(child > 0){
            //判断是否需要交换
            E o1 = (E)arrays[child];
            E o2 = (E)arrays[parent];
            if(o1.compareTo(o2) < 0){
                Object tem = arrays[child];
                arrays[child] = arrays[parent];
                arrays[parent] = tem;
                child = parent;
                parent = (child - 1) / 2;
            }else break;//满足小根堆的定义
        }

    }

    public boolean offer(Object data){

        //对象为空
        if(data == null) return false;

        //扩容：小于64 ，2倍扩容 大于64 1.5倍扩容
        if(arrays.length == size){
            if(size < 64)
               arrays = Arrays.copyOf(arrays,size * 2);
            else{
                int capacity = (int)(size * 1.5);
                arrays = Arrays.copyOf(arrays,capacity);
            }
        }

        //拷贝失败
        if(arrays == null) return false;

        //加入元素
        arrays[size] = data;

        //向上调整
        siftUp(size++);

        return true;
    }
    public E poll(){
        //出队列元素不能为空
        if(size == 0) throw new NullPointerException();

        int top = 0,bottom = size - 1;//队头和对位元素

        //1.交换
        Object tem = arrays[top];
        arrays[top] = arrays[bottom];
        arrays[bottom] = tem;

        //2.向下调整
        siftDown(0);
        E ret = (E)arrays[size-- - 1];

        //3.返回
        return ret;
    }

    public E peek(){
        //没有元素，抛异常
        if(size() == 0) throw new NullPointerException("没有元素，不可查看");

        return (E)arrays[0];
    }

    public int size(){
        return size;
    }

    public Boolean isEmpty(){
        return size == 0;
    }

    public void clear(){
        arrays = null;
        size = 0;
    }

    public static void main(String[] args) {
        HashSet s = new HashSet();
        s.toArray();

        Collection collection = new ArrayList();
        collection.add(162);
        collection.add(21);
        collection.add(145);

        MyPriorityQueue<Integer> priorityQueue = new MyPriorityQueue<>(collection);

        System.out.println(priorityQueue.peek());
    }

    public static void main3(String[] args) {
        //2.指定容量
        MyPriorityQueue<Integer> priorityQueue = new MyPriorityQueue<Integer>(1);

        //增加元素
        priorityQueue.offer(666);

        //获取队列顶部元素
        System.out.println(priorityQueue.peek());

        //判断是否为空
        System.out.println(priorityQueue.isEmpty());

        //回收队列
        priorityQueue.clear();

        //此时不能使用对象引用
        priorityQueue.offer(1);

    }
    public static void main2(String[] args) {
        MyPriorityQueue<String> myPriorityQueue = new MyPriorityQueue<>();
        myPriorityQueue.offer("c");
        myPriorityQueue.offer("b");
        myPriorityQueue.offer("a");

        System.out.println("队列顶部元素 ：" + myPriorityQueue.peek());//a
        System.out.println("队列大小: " + myPriorityQueue.size());//0

        myPriorityQueue.poll();//a
        System.out.println("出队列的元素：" + myPriorityQueue.poll());//b
        System.out.println("出队列的元素：" + myPriorityQueue.poll());//c


        System.out.println(myPriorityQueue.poll());//没有元素，抛异常
    }
    public static void main1(String[] args) {
        int[] arr = {1,2,3,4};
        MyPriorityQueue myPriorityQueue = new MyPriorityQueue();
       // myPriorityQueue.delete(arr);
        //myPriorityQueue.siftUp(arr,4);
        //MyPriorityQueue.creatHeap(arr);
    }

    public  void creatHeap(int[] arr){
        int root = (arr.length - 2) / 2;
        for (; root >= 0 ; root--) {
            siftDown(root);
        }
    }
}
